class Solution:
    # def exist(self, board, word: str) -> bool:
    #     def dfs(i, j, k):
    #         if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
    #             return False
    #         if k == len(word) - 1: return True
    #         tmp, board[i][j] = board[i][j], '/'
    #         res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
    #         board[i][j] = tmp
    #         return res
    #
    #     for i in range(len(board)):
    #         for j in range(len(board[0])):
    #             if dfs(i, j, 0):
    #                 return True
    #     return False

    def exist(self, board, word: str) -> bool:
        len_word = len(word)-1
        def dfs(i,j,k):
            print(i,j,k)
            if not 0<=i < len(board) or not 0<=j < len(board[0]) or board[i][j]!=word[k]:
                return False
            if k == len_word:
                return True
            tem = board[i][j]
            board[i][j] = 'null'
            res = dfs(i-1,j,k+1) or dfs(i+1,j,k+1) or dfs(i,j-1,k+1) or dfs(i,j+1,k+1)
            board[i][j] = tem
            return res

        for i in range(0,len(board)):
            for j in range(0,len(board[0])):
                if dfs(i,j,0):
                    return True
        return False


ans = Solution()
xx = ans.exist(board =[["a","a","a","a"],["a","a","a","a"],["a","a","a","a"]],word="aaaaaaaaaaaa")
print(xx)